import java.util.ArrayList;
import java.util.List;

/**
 * 131. Palindrome Partitioning 分割回文串
 * https://leetcode.com/problems/palindrome-partitioning/
 */
class PalindromePartitioning {
    private final List<List<String>> ans = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private String s;

    /**
     * 方法：回溯算法
     * 
     * Args:
     *   s: String - 输入的字符串
     * 
     * Returns:
     *   List<List<String>> - 所有可能的回文分割
     * 
     * Time: O(n * 2^n) - 共有2^n个分割，每个分割需要O(n)时间复制
     * Space: O(n) - 递归栈深度为n，path数组长度为n
     */
    public List<List<String>> partition(String s) {
        this.s = s;
        backtrack(0);
        return ans;
    }

    private void backtrack(int i){
        if(i == s.length()){// s 分割完毕
            ans.add(new ArrayList(path));
            return;
        }
        for(int j = i; j < s.length(); j++){// 枚举子串的结束位置
            if(isPalindrome(i, j)){ //判断是否回文传
                path.add(s.substring(i, j + 1));
                backtrack(j+1);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(int left, int right){
        while(left < right){
            if(s.charAt(left++) != s.charAt(right--)){
                return false;
            }
        }
        return true;
    }
}